package com.lw.leetcode.arr.c;

import com.lw.test.util.Utils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * 2449. 使数组相似的最少操作次数
 *
 * @author liw
 * @version 1.0
 * @date 2022/10/24 13:43
 */
public class MakeSimilar {

    public static void main(String[] args) {
        MakeSimilar test = new MakeSimilar();

        // 2
//        int[] nums = {8, 12, 6};
//        int[] target = {2, 14, 10};

        // 2
//        int[] nums = {1, 2, 5};
//        int[] target = {4, 1, 3};

        // 0
//        int[] nums = {1, 1, 1, 1, 1};
//        int[] target = {1, 1, 1, 1, 1};

        // 0
        int[] nums = Utils.getArr(10000, 1002, 100000);

        int[] target = new int[nums.length];
        int length = nums.length;

        for (int i = 0; i < length; i++) {
            target[i] = nums[i];
        }
        for (int i = 0; i < 100000; i++) {
            int a1 = (int) (Math.random() * length);
            int a2 = (int) (Math.random() * length);
            int v = (int) (Math.random() * 500);
            v = v << 1;
            if (v >= target[a2] || target[a1] + v > 1000000) {
                continue;
            }
            target[a1] += v;
            target[a2] -= v;
        }
        System.out.println(Arrays.toString(target));

        long l = test.makeSimilar(nums, target);
        System.out.println(l);
    }

    public long makeSimilar(int[] nums, int[] target) {
        long sum = 0;
        Arrays.sort(nums);
        Arrays.sort(target);
        List<Integer> a0 = new ArrayList<>();
        List<Integer> a1 = new ArrayList<>();
        for (int num : nums) {
            if ((num & 1) == 0) {
                a0.add(num);
            } else {
                a1.add(num);
            }
        }
        List<Integer> b0 = new ArrayList<>(a0.size());
        List<Integer> b1 = new ArrayList<>(a1.size());
        for (int num : target) {
            if ((num & 1) == 0) {
                b0.add(num);
            } else {
                b1.add(num);
            }
        }
        int size = a0.size();
        for (int i = 0; i < size; i++) {
            sum += (Math.abs(a0.get(i) - b0.get(i)) >> 1);
        }
        size = a1.size();
        for (int i = 0; i < size; i++) {
            sum += (Math.abs(a1.get(i) - b1.get(i)) >> 1);
        }
        return sum >> 1;
    }

}
